home *** CD-ROM | disk | FTP | other *** search
/ Programming Languages Suite / ProgramD2.iso / Borland / Borland Pascal with Objects 7.0 / GREPDLL.ZIP / REGEXP.C < prev    next >
Encoding:
C/C++ Source or Header  |  1992-10-27  |  27.0 KB  |  1,170 lines
  1. /************************************************\
  2. *                                                *
  3. *   REGEXP.DDL Implementation Module             *
  4. *   Copyright (c) 1992 by Borland International  *
  5. *   Copyright (c) 1986 by Univerisity of Toronto *
  6. *                                                *
  7. \************************************************/
  8.  
  9. /* This file was originally written by Henry Spencer for
  10.  * the University of Toronto and was modified by
  11.  * Borland International to compile with Borland C++ 3.1
  12.  * and for use in a DLL.
  13.  */
  14.  
  15. #include <stdio.h>
  16. #include <string.h>
  17.  
  18. #include "_regexp.h"
  19.  
  20. /*
  21.  * The "internal use only" fields in regexp.h are present to pass info from
  22.  * compile to execute that permits the execute phase to run lots faster on
  23.  * simple cases.  They are:
  24.  *
  25.  * regstart    char that must begin a match; '\0' if none obvious
  26.  * reganch    is the match anchored (at beginning-of-line only)?
  27.  * regmust    string (pointer into program) that match must include, or NULL
  28.  * regmlen    length of regmust string
  29.  *
  30.  * Regstart and reganch permit very fast decisions on suitable starting points
  31.  * for a match, cutting down the work a lot.  Regmust permits fast rejection
  32.  * of lines that cannot possibly match.  The regmust tests are costly enough
  33.  * that regcomp() supplies a regmust only if the r.e. contains something
  34.  * potentially expensive (at present, the only such thing detected is * or +
  35.  * at the start of the r.e., which can involve a lot of backup).  Regmlen is
  36.  * supplied because the test in regexec() needs it and regcomp() is computing
  37.  * it anyway.
  38.  */
  39.  
  40. /*
  41.  * Structure for regexp "program".  This is essentially a linear encoding
  42.  * of a nondeterministic finite-state machine (aka syntax charts or
  43.  * "railroad normal form" in parsing technology).  Each node is an opcode
  44.  * plus a "next" pointer, possibly plus an operand.  "Next" pointers of
  45.  * all nodes except BRANCH implement concatenation; a "next" pointer with
  46.  * a BRANCH on both ends of it is connecting two alternatives.  (Here we
  47.  * have one of the subtle syntax dependencies:  an individual BRANCH (as
  48.  * opposed to a collection of them) is never concatenated with anything
  49.  * because of operator precedence.)  The operand of some types of node is
  50.  * a literal string; for others, it is a node leading into a sub-FSM.  In
  51.  * particular, the operand of a BRANCH node is the first node of the branch.
  52.  * (NB this is *not* a tree structure:  the tail of the branch connects
  53.  * to the thing following the set of BRANCHes.)  The opcodes are:
  54.  */
  55.  
  56. /* definition    number    opnd?    meaning */
  57. #define    END    0    /* no    End of program. */
  58. #define    BOL    1    /* no    Match "" at beginning of line. */
  59. #define    EOL    2    /* no    Match "" at end of line. */
  60. #define    ANY    3    /* no    Match any one character. */
  61. #define    ANYOF    4    /* str    Match any character in this string. */
  62. #define    ANYBUT    5    /* str    Match any character not in this string. */
  63. #define    BRANCH    6    /* node    Match this alternative, or the next... */
  64. #define    BACK    7    /* no    Match "", "next" ptr points backward. */
  65. #define    EXACTLY    8    /* str    Match this string. */
  66. #define    NOTHING    9    /* no    Match empty string. */
  67. #define    STAR    10    /* node    Match this (simple) thing 0 or more times. */
  68. #define    PLUS    11    /* node    Match this (simple) thing 1 or more times. */
  69. #define    OPEN    20    /* no    Mark this point in input as start of #n. */
  70.             /*    OPEN+1 is number 1, etc. */
  71. #define    CLOSE    30    /* no    Analogous to OPEN. */
  72.  
  73. /*
  74.  * Opcode notes:
  75.  *
  76.  * BRANCH    The set of branches constituting a single choice are hooked
  77.  *        together with their "next" pointers, since precedence prevents
  78.  *        anything being concatenated to any individual branch.  The
  79.  *        "next" pointer of the last BRANCH in a choice points to the
  80.  *        thing following the whole choice.  This is also where the
  81.  *        final "next" pointer of each individual branch points; each
  82.  *        branch starts with the operand node of a BRANCH node.
  83.  *
  84.  * BACK        Normal "next" pointers all implicitly point forward; BACK
  85.  *        exists to make loop structures possible.
  86.  *
  87.  * STAR,PLUS    '?', and complex '*' and '+', are implemented as circular
  88.  *        BRANCH structures using BACK.  Simple cases (one character
  89.  *        per match) are implemented with STAR and PLUS for speed
  90.  *        and to minimize recursive plunges.
  91.  *
  92.  * OPEN,CLOSE    ...are numbered at compile time.
  93.  */
  94.  
  95. /*
  96.  * A node is one char of opcode followed by two chars of "next" pointer.
  97.  * "Next" pointers are stored as two 8-bit pieces, high order first.  The
  98.  * value is a positive offset from the opcode of the node containing it.
  99.  * An operand, if any, simply follows the node.  (Note that much of the
  100.  * code generation knows about this implicit relationship.)
  101.  *
  102.  * Using two bytes for the "next" pointer is vast overkill for most things,
  103.  * but allows patterns to get big without disasters.
  104.  */
  105. #define    OP(p)    (*(p))
  106. #define    NEXT(p)    (((*((p)+1)&0377)<<8) + (*((p)+2)&0377))
  107. #define    OPERAND(p)    ((p) + 3)
  108.  
  109. /*
  110.  * See _regex.h for one further detail of program structure.
  111.  */
  112.  
  113.  
  114. /*
  115.  * Utility definitions.
  116.  */
  117. #ifndef CHARBITS
  118. #define    UCHARAT(p)    ((int)*(unsigned char *)(p))
  119. #else
  120. #define    UCHARAT(p)    ((int)*(p)&CHARBITS)
  121. #endif
  122.  
  123. #define    FAIL(m)    { regerror = m; return(NULL); }
  124. #define    ISMULT(c)    ((c) == '*' || (c) == '+' || (c) == '?')
  125. #define    META    "^$.[()|?+*\\"
  126.  
  127. /*
  128.  * Flags to be passed up and down.
  129.  */
  130. #define    HASWIDTH    01    /* Known never to match null string. */
  131. #define    SIMPLE        02    /* Simple enough to be STAR/PLUS operand. */
  132. #define    SPSTART        04    /* Starts with * or +. */
  133. #define    WORST        0    /* Worst case. */
  134.  
  135. /*
  136.  * Global work variables for regcomp().
  137.  */
  138. static const char *regparse;    /* Input-scan pointer. */
  139. static int regnpar;                /* () count. */
  140. static char regdummy;
  141. static char *regcode;            /* Code-emit pointer; ®dummy = don't. */
  142. static long regsize;            /* Code size. */
  143.  
  144. /*
  145.  * Forward declarations for regcomp()'s friends.
  146.  */
  147. #ifndef STATIC
  148. #define    STATIC    static
  149. #endif
  150. STATIC char *reg();
  151. STATIC char *regbranch();
  152. STATIC char *regpiece();
  153. STATIC char *regatom();
  154. STATIC char *regnode();
  155. STATIC char *regnext();
  156. STATIC void regc();
  157. STATIC void reginsert();
  158. STATIC void regtail();
  159. STATIC void regoptail();
  160. #ifdef STRCSPN
  161. STATIC int strcspn();
  162. #endif
  163.  
  164. int regerror;
  165.  
  166. /*
  167.  - regcomp - compile a regular expression into internal code
  168.  *
  169.  * We can't allocate space until we know how big the compiled form will be,
  170.  * but we can't compile it (and thus know how big it is) until we've got a
  171.  * place to put the code.  So we cheat:  we compile it twice, once with code
  172.  * generation turned off and size counting turned on, and once "for real".
  173.  * This also means that we don't allocate space until we are sure that the
  174.  * thing really will compile successfully, and we never have to move the
  175.  * code and thus invalidate pointers into it.  (Note that it has to be in
  176.  * one piece because free() must be able to free it all.)
  177.  *
  178.  * Beware that the optimization-preparation code in here knows about some
  179.  * of the structure of the compiled regexp.
  180.  */
  181. regexp *regcomp(const char *exp)
  182. {
  183.     register regexp *r;
  184.     register char *scan;
  185.     register char *longest;
  186.     register int len;
  187.     int flags;
  188.     extern char *malloc();
  189.  
  190.     if (exp == NULL)
  191.         FAIL(RE_INVALIDPARAMETER);
  192.  
  193.     /* First pass: determine size, legality. */
  194.     regparse = exp;
  195.     regnpar = 1;
  196.     regsize = 0L;
  197.     regcode = ®dummy;
  198.     regc(MAGIC);
  199.     if (reg(0, &flags) == NULL)
  200.         return(NULL);
  201.  
  202.     /* Small enough for pointer-storage convention? */
  203.     if (regsize >= 32767L)        /* Probably could be 65535L. */
  204.         FAIL(RE_EXPRESSIONTOOBIG);
  205.  
  206.     /* Allocate space. */
  207.     r = (regexp *)malloc(sizeof(regexp) + (unsigned)regsize);
  208.     if (r == NULL)
  209.         FAIL(RE_OUTOFMEMORY);
  210.  
  211.     /* Second pass: emit code. */
  212.     regparse = exp;
  213.     regnpar = 1;
  214.     regcode = r->program;
  215.     regc(MAGIC);
  216.     if (reg(0, &flags) == NULL)
  217.         return(NULL);
  218.  
  219.     /* Dig out information for optimizations. */
  220.     r->regstart = '\0';    /* Worst-case defaults. */
  221.     r->reganch = 0;
  222.     r->regmust = NULL;
  223.     r->regmlen = 0;
  224.     scan = r->program+1;            /* First BRANCH. */
  225.     if (OP(regnext(scan)) == END) {        /* Only one top-level choice. */
  226.         scan = OPERAND(scan);
  227.  
  228.         /* Starting-point info. */
  229.         if (OP(scan) == EXACTLY)
  230.             r->regstart = *OPERAND(scan);
  231.         else if (OP(scan) == BOL)
  232.             r->reganch++;
  233.  
  234.         /*
  235.          * If there's something expensive in the r.e., find the
  236.          * longest literal string that must appear and make it the
  237.          * regmust.  Resolve ties in favor of later strings, since
  238.          * the regstart check works with the beginning of the r.e.
  239.          * and avoiding duplication strengthens checking.  Not a
  240.          * strong reason, but sufficient in the absence of others.
  241.          */
  242.         if (flags&SPSTART) {
  243.             longest = NULL;
  244.             len = 0;
  245.             for (; scan != NULL; scan = regnext(scan))
  246.                 if (OP(scan) == EXACTLY && strlen(OPERAND(scan)) >= len) {
  247.                     longest = OPERAND(scan);
  248.                     len = strlen(OPERAND(scan));
  249.                 }
  250.             r->regmust = longest;
  251.             r->regmlen = len;
  252.         }
  253.     }
  254.  
  255.     return(r);
  256. }
  257.  
  258. /*
  259.  - reg - regular expression, i.e. main body or parenthesized thing
  260.  *
  261.  * Caller must absorb opening parenthesis.
  262.  *
  263.  * Combining parenthesis handling with the base level of regular expression
  264.  * is a trifle forced, but the need to tie the tails of the branches to what
  265.  * follows makes it hard to avoid.
  266.  */
  267. static char *reg(int paren, int *flagp)
  268. {
  269.     register char *ret;
  270.     register char *br;
  271.     register char *ender;
  272.     register int parno;
  273.     int flags;
  274.  
  275.     *flagp = HASWIDTH;    /* Tentatively. */
  276.  
  277.     /* Make an OPEN node, if parenthesized. */
  278.     if (paren) {
  279.         if (regnpar >= NSUBEXP)
  280.             FAIL(RE_TOOMANYSUBEXPS);
  281.         parno = regnpar;
  282.         regnpar++;
  283.         ret = regnode(OPEN+parno);
  284.     } else
  285.         ret = NULL;
  286.  
  287.     /* Pick up the branches, linking them together. */
  288.     br = regbranch(&flags);
  289.     if (br == NULL)
  290.         return(NULL);
  291.     if (ret != NULL)
  292.         regtail(ret, br);    /* OPEN -> first. */
  293.     else
  294.         ret = br;
  295.     if (!(flags&HASWIDTH))
  296.         *flagp &= ~HASWIDTH;
  297.     *flagp |= flags&SPSTART;
  298.     while (*regparse == '|') {
  299.         regparse++;
  300.         br = regbranch(&flags);
  301.         if (br == NULL)
  302.             return(NULL);
  303.         regtail(ret, br);    /* BRANCH -> BRANCH. */
  304.         if (!(flags&HASWIDTH))
  305.             *flagp &= ~HASWIDTH;
  306.         *flagp |= flags&SPSTART;
  307.     }
  308.  
  309.     /* Make a closing node, and hook it on the end. */
  310.     ender = regnode((paren) ? CLOSE+parno : END);    
  311.     regtail(ret, ender);
  312.  
  313.     /* Hook the tails of the branches to the closing node. */
  314.     for (br = ret; br != NULL; br = regnext(br))
  315.         regoptail(br, ender);
  316.  
  317.     /* Check for proper termination. */
  318.     if (paren && *regparse++ != ')') {
  319.         FAIL(RE_UNMATCHEDPARENS);
  320.     } else if (!paren && *regparse != '\0') {
  321.         if (*regparse == ')') {
  322.             FAIL(RE_UNMATCHEDPARENS);
  323.         } else
  324.             FAIL(RE_INTERNAL);
  325.         /* NOTREACHED */
  326.     }
  327.  
  328.     return(ret);
  329. }
  330.  
  331. /*
  332.  - regbranch - one alternative of an | operator
  333.  *
  334.  * Implements the concatenation operator.
  335.  */
  336. static char *
  337. regbranch(flagp)
  338. int *flagp;
  339. {
  340.     register char *ret;
  341.     register char *chain;
  342.     register char *latest;
  343.     int flags;
  344.  
  345.     *flagp = WORST;        /* Tentatively. */
  346.  
  347.     ret = regnode(BRANCH);
  348.     chain = NULL;
  349.     while (*regparse != '\0' && *regparse != '|' && *regparse != ')') {
  350.         latest = regpiece(&flags);
  351.         if (latest == NULL)
  352.             return(NULL);
  353.         *flagp |= flags&HASWIDTH;
  354.         if (chain == NULL)    /* First piece. */
  355.             *flagp |= flags&SPSTART;
  356.         else
  357.             regtail(chain, latest);
  358.         chain = latest;
  359.     }
  360.     if (chain == NULL)    /* Loop ran zero times. */
  361.         (void) regnode(NOTHING);
  362.  
  363.     return(ret);
  364. }
  365.  
  366. /*
  367.  - regpiece - something followed by possible [*+?]
  368.  *
  369.  * Note that the branching code sequences used for ? and the general cases
  370.  * of * and + are somewhat optimized:  they use the same NOTHING node as
  371.  * both the endmarker for their branch list and the body of the last branch.
  372.  * It might seem that this node could be dispensed with entirely, but the
  373.  * endmarker role is not redundant.
  374.  */
  375. static char *
  376. regpiece(flagp)
  377. int *flagp;
  378. {
  379.     register char *ret;
  380.     register char op;
  381.     register char *next;
  382.     int flags;
  383.  
  384.     ret = regatom(&flags);
  385.     if (ret == NULL)
  386.         return(NULL);
  387.  
  388.     op = *regparse;
  389.     if (!ISMULT(op)) {
  390.         *flagp = flags;
  391.         return(ret);
  392.     }
  393.  
  394.     if (!(flags&HASWIDTH) && op != '?')
  395.         FAIL(RE_INVALIDREPEAT);
  396.     *flagp = (op != '+') ? (WORST|SPSTART) : (WORST|HASWIDTH);
  397.  
  398.     if (op == '*' && (flags&SIMPLE))
  399.         reginsert(STAR, ret);
  400.     else if (op == '*') {
  401.         /* Emit x* as (x&|), where & means "self". */
  402.         reginsert(BRANCH, ret);            /* Either x */
  403.         regoptail(ret, regnode(BACK));        /* and loop */
  404.         regoptail(ret, ret);            /* back */
  405.         regtail(ret, regnode(BRANCH));        /* or */
  406.         regtail(ret, regnode(NOTHING));        /* null. */
  407.     } else if (op == '+' && (flags&SIMPLE))
  408.         reginsert(PLUS, ret);
  409.     else if (op == '+') {
  410.         /* Emit x+ as x(&|), where & means "self". */
  411.         next = regnode(BRANCH);            /* Either */
  412.         regtail(ret, next);
  413.         regtail(regnode(BACK), ret);        /* loop back */
  414.         regtail(next, regnode(BRANCH));        /* or */
  415.         regtail(ret, regnode(NOTHING));        /* null. */
  416.     } else if (op == '?') {
  417.         /* Emit x? as (x|) */
  418.         reginsert(BRANCH, ret);            /* Either x */
  419.         regtail(ret, regnode(BRANCH));        /* or */
  420.         next = regnode(NOTHING);        /* null. */
  421.         regtail(ret, next);
  422.         regoptail(ret, next);
  423.     }
  424.     regparse++;
  425.     if (ISMULT(*regparse))
  426.         FAIL(RE_NESTEDREPEAT);
  427.  
  428.     return(ret);
  429. }
  430.  
  431. #pragma warn -rch
  432.  
  433. /*
  434.  - regatom - the lowest level
  435.  *
  436.  * Optimization:  gobbles an entire sequence of ordinary characters so that
  437.  * it can turn them into a single node, which is smaller to store and
  438.  * faster to run.  Backslashed characters are exceptions, each becoming a
  439.  * separate node; the code is simpler that way and it's not worth fixing.
  440.  */
  441. static char *
  442. regatom(flagp)
  443. int *flagp;
  444. {
  445.     register char *ret;
  446.     int flags;
  447.  
  448.     *flagp = WORST;        /* Tentatively. */
  449.  
  450.     switch (*regparse++) {
  451.     case '^':
  452.         ret = regnode(BOL);
  453.         break;
  454.     case '$':
  455.         ret = regnode(EOL);
  456.         break;
  457.     case '.':
  458.         ret = regnode(ANY);
  459.         *flagp |= HASWIDTH|SIMPLE;
  460.         break;
  461.     case '[': {
  462.             register int class;
  463.             register int classend;
  464.  
  465.             if (*regparse == '^') {    /* Complement of range. */
  466.                 ret = regnode(ANYBUT);
  467.                 regparse++;
  468.             } else
  469.                 ret = regnode(ANYOF);
  470.             if (*regparse == ']' || *regparse == '-')
  471.                 regc(*regparse++);
  472.             while (*regparse != '\0' && *regparse != ']') {
  473.                 if (*regparse == '-') {
  474.                     regparse++;
  475.                     if (*regparse == ']' || *regparse == '\0')
  476.                         regc('-');
  477.                     else {
  478.                         class = UCHARAT(regparse-2)+1;
  479.                         classend = UCHARAT(regparse);
  480.                         if (class > classend+1)
  481.                             FAIL(RE_INVALIDRANGE);
  482.                         for (; class <= classend; class++)
  483.                             regc(class);
  484.                         regparse++;
  485.                     }
  486.                 } else
  487.                     regc(*regparse++);
  488.             }
  489.             regc('\0');
  490.             if (*regparse != ']')
  491.                 FAIL(RE_UNMATCHEDBRACKET);
  492.             regparse++;
  493.             *flagp |= HASWIDTH|SIMPLE;
  494.         }
  495.         break;
  496.     case '(':
  497.         ret = reg(1, &flags);
  498.         if (ret == NULL)
  499.             return(NULL);
  500.         *flagp |= flags&(HASWIDTH|SPSTART);
  501.         break;
  502.     case '\0':
  503.     case '|':
  504.     case ')':
  505.         FAIL(RE_INTERNAL);    /* Supposed to be caught earlier. */
  506.         break;
  507.     case '?':
  508.     case '+':
  509.     case '*':
  510.         FAIL(RE_INVALIDREPEAT);
  511.         break;
  512.     case '\\':
  513.         if (*regparse == '\0')
  514.             FAIL(RE_TRAILINGBACKSLASH);
  515.         ret = regnode(EXACTLY);
  516.         regc(*regparse++);
  517.         regc('\0');
  518.         *flagp |= HASWIDTH|SIMPLE;
  519.         break;
  520.     default: {
  521.             register int len;
  522.             register char ender;
  523.  
  524.             regparse--;
  525.             len = strcspn(regparse, META);
  526.             if (len <= 0)
  527.                 FAIL(RE_INTERNAL);
  528.             ender = *(regparse+len);
  529.             if (len > 1 && ISMULT(ender))
  530.                 len--;        /* Back off clear of ?+* operand. */
  531.             *flagp |= HASWIDTH;
  532.             if (len == 1)
  533.                 *flagp |= SIMPLE;
  534.             ret = regnode(EXACTLY);
  535.             while (len > 0) {
  536.                 regc(*regparse++);
  537.                 len--;
  538.             }
  539.             regc('\0');
  540.         }
  541.         break;
  542.     }
  543.  
  544.     return(ret);
  545. }
  546.  
  547. /*
  548.  - regnode - emit a node
  549.  */
  550. static char *            /* Location. */
  551. regnode(op)
  552. char op;
  553. {
  554.     register char *ret;
  555.     register char *ptr;
  556.  
  557.     ret = regcode;
  558.     if (ret == ®dummy) {
  559.         regsize += 3;
  560.         return(ret);
  561.     }
  562.  
  563.     ptr = ret;
  564.     *ptr++ = op;
  565.     *ptr++ = '\0';        /* Null "next" pointer. */
  566.     *ptr++ = '\0';
  567.     regcode = ptr;
  568.  
  569.     return(ret);
  570. }
  571.  
  572. /*
  573.  - regc - emit (if appropriate) a byte of code
  574.  */
  575. static void
  576. regc(b)
  577. char b;
  578. {
  579.     if (regcode != ®dummy)
  580.         *regcode++ = b;
  581.     else
  582.         regsize++;
  583. }
  584.  
  585. /*
  586.  - reginsert - insert an operator in front of already-emitted operand
  587.  *
  588.  * Means relocating the operand.
  589.  */
  590. static void
  591. reginsert(op, opnd)
  592. char op;
  593. char *opnd;
  594. {
  595.     register char *src;
  596.     register char *dst;
  597.     register char *place;
  598.  
  599.     if (regcode == ®dummy) {
  600.         regsize += 3;
  601.         return;
  602.     }
  603.  
  604.     src = regcode;
  605.     regcode += 3;
  606.     dst = regcode;
  607.     while (src > opnd)
  608.         *--dst = *--src;
  609.  
  610.     place = opnd;        /* Op node, where operand used to be. */
  611.     *place++ = op;
  612.     *place++ = '\0';
  613.     *place++ = '\0';
  614. }
  615.  
  616. /*
  617.  - regtail - set the next-pointer at the end of a node chain
  618.  */
  619. static void
  620. regtail(p, val)
  621. char *p;
  622. char *val;
  623. {
  624.     register char *scan;
  625.     register char *temp;
  626.     register int offset;
  627.  
  628.     if (p == ®dummy)
  629.         return;
  630.  
  631.     /* Find last node. */
  632.     scan = p;
  633.     for (;;) {
  634.         temp = regnext(scan);
  635.         if (temp == NULL)
  636.             break;
  637.         scan = temp;
  638.     }
  639.  
  640.     if (OP(scan) == BACK)
  641.         offset = scan - val;
  642.     else
  643.         offset = val - scan;
  644.     *(scan+1) = (offset>>8)&0377;
  645.     *(scan+2) = offset&0377;
  646. }
  647.  
  648. /*
  649.  - regoptail - regtail on operand of first argument; nop if operandless
  650.  */
  651. static void
  652. regoptail(p, val)
  653. char *p;
  654. char *val;
  655. {
  656.     /* "Operandless" and "op != BRANCH" are synonymous in practice. */
  657.     if (p == NULL || p == ®dummy || OP(p) != BRANCH)
  658.         return;
  659.     regtail(OPERAND(p), val);
  660. }
  661.  
  662. /*
  663.  * regexec and friends
  664.  */
  665.  
  666. /*
  667.  * Global work variables for regexec().
  668.  */
  669. static char *reginput;            /* String-input pointer. */
  670. static const char *regbol;        /* Beginning of input, for ^ check. */
  671. static char **regstartp;        /* Pointer to startp array. */
  672. static char **regendp;            /* Ditto for endp. */
  673.  
  674. /*
  675.  * Forwards.
  676.  */
  677. STATIC int regtry();
  678. STATIC int regmatch();
  679. STATIC int regrepeat();
  680.  
  681. #ifdef DEBUG
  682. int regnarrate = 0;
  683. void regdump();
  684. STATIC char *regprop();
  685. #endif
  686.  
  687. /*
  688.  - regexec - match a regexp against a string
  689.  */
  690. int regexec(register regexp *prog, register const char *string)
  691. {
  692.     register const char *s;
  693.     extern char *strchr();
  694.  
  695.     /* Be paranoid... */
  696.     if (prog == NULL || string == NULL) {
  697.         regerror = RE_INVALIDPARAMETER;
  698.         return(0);
  699.     }
  700.  
  701.     /* Check validity of program. */
  702.     if (UCHARAT(prog->program) != MAGIC) {
  703.         regerror = RE_INVALIDPARAMETER;
  704.         return(0);
  705.     }
  706.  
  707.     /* If there is a "must appear" string, look for it. */
  708.     if (prog->regmust != NULL) {
  709.         s = string;
  710.         while ((s = strchr(s, prog->regmust[0])) != NULL) {
  711.             if (strncmp(s, prog->regmust, prog->regmlen) == 0)
  712.                 break;    /* Found it. */
  713.             s++;
  714.         }
  715.         if (s == NULL)    /* Not present. */
  716.             return(0);
  717.     }
  718.  
  719.     /* Mark beginning of line for ^ . */
  720.     regbol = string;
  721.  
  722.     /* Simplest case:  anchored match need be tried only once. */
  723.     if (prog->reganch)
  724.         return(regtry(prog, string));
  725.  
  726.     /* Messy cases:  unanchored match. */
  727.     s = string;
  728.     if (prog->regstart != '\0')
  729.         /* We know what char it must start with. */
  730.         while ((s = strchr(s, prog->regstart)) != NULL) {
  731.             if (regtry(prog, s))
  732.                 return(1);
  733.             s++;
  734.         }
  735.     else
  736.         /* We don't -- general case. */
  737.         do {
  738.             if (regtry(prog, s))
  739.                 return(1);
  740.         } while (*s++ != '\0');
  741.  
  742.     /* Failure. */
  743.     return(0);
  744. }
  745.  
  746. /*
  747.  - regtry - try match at specific point
  748.  */
  749. static int            /* 0 failure, 1 success */
  750. regtry(prog, string)
  751. regexp *prog;
  752. char *string;
  753. {
  754.     register int i;
  755.     register char **sp;
  756.     register char **ep;
  757.  
  758.     reginput = string;
  759.     regstartp = prog->startp;
  760.     regendp = prog->endp;
  761.  
  762.     sp = prog->startp;
  763.     ep = prog->endp;
  764.     for (i = NSUBEXP; i > 0; i--) {
  765.         *sp++ = NULL;
  766.         *ep++ = NULL;
  767.     }
  768.     if (regmatch(prog->program + 1)) {
  769.         prog->startp[0] = string;
  770.         prog->endp[0] = reginput;
  771.         return(1);
  772.     } else
  773.         return(0);
  774. }
  775.  
  776. /*
  777.  - regmatch - main matching routine
  778.  *
  779.  * Conceptually the strategy is simple:  check to see whether the current
  780.  * node matches, call self recursively to see whether the rest matches,
  781.  * and then act accordingly.  In practice we make some effort to avoid
  782.  * recursion, in particular by going through "ordinary" nodes (that don't
  783.  * need to know whether the rest of the match failed) by a loop instead of
  784.  * by recursion.
  785.  */
  786. static int            /* 0 failure, 1 success */
  787. regmatch(prog)
  788. char *prog;
  789. {
  790.     register char *scan;    /* Current node. */
  791.     char *next;        /* Next node. */
  792.     extern char *strchr();
  793.  
  794.     scan = prog;
  795. #ifdef DEBUG
  796.     if (scan != NULL && regnarrate)
  797.         fprintf(stderr, "%s(\n", regprop(scan));
  798. #endif
  799.     while (scan != NULL) {
  800. #ifdef DEBUG
  801.         if (regnarrate)
  802.             fprintf(stderr, "%s...\n", regprop(scan));
  803. #endif
  804.         next = regnext(scan);
  805.  
  806.         switch (OP(scan)) {
  807.         case BOL:
  808.             if (reginput != regbol)
  809.                 return(0);
  810.             break;
  811.         case EOL:
  812.             if (*reginput != '\0')
  813.                 return(0);
  814.             break;
  815.         case ANY:
  816.             if (*reginput == '\0')
  817.                 return(0);
  818.             reginput++;
  819.             break;
  820.         case EXACTLY: {
  821.                 register int len;
  822.                 register char *opnd;
  823.  
  824.                 opnd = OPERAND(scan);
  825.                 /* Inline the first character, for speed. */
  826.                 if (*opnd != *reginput)
  827.                     return(0);
  828.                 len = strlen(opnd);
  829.                 if (len > 1 && strncmp(opnd, reginput, len) != 0)
  830.                     return(0);
  831.                 reginput += len;
  832.             }
  833.             break;
  834.         case ANYOF:
  835.             if (*reginput == '\0' || strchr(OPERAND(scan), *reginput) == NULL)
  836.                 return(0);
  837.             reginput++;
  838.             break;
  839.         case ANYBUT:
  840.             if (*reginput == '\0' || strchr(OPERAND(scan), *reginput) != NULL)
  841.                 return(0);
  842.             reginput++;
  843.             break;
  844.         case NOTHING:
  845.             break;
  846.         case BACK:
  847.             break;
  848.         case OPEN+1:
  849.         case OPEN+2:
  850.         case OPEN+3:
  851.         case OPEN+4:
  852.         case OPEN+5:
  853.         case OPEN+6:
  854.         case OPEN+7:
  855.         case OPEN+8:
  856.         case OPEN+9: {
  857.                 register int no;
  858.                 register char *save;
  859.  
  860.                 no = OP(scan) - OPEN;
  861.                 save = reginput;
  862.  
  863.                 if (regmatch(next)) {
  864.                     /*
  865.                      * Don't set startp if some later
  866.                      * invocation of the same parentheses
  867.                      * already has.
  868.                      */
  869.                     if (regstartp[no] == NULL)
  870.                         regstartp[no] = save;
  871.                     return(1);
  872.                 } else
  873.                     return(0);
  874.             }
  875.             break;
  876.         case CLOSE+1:
  877.         case CLOSE+2:
  878.         case CLOSE+3:
  879.         case CLOSE+4:
  880.         case CLOSE+5:
  881.         case CLOSE+6:
  882.         case CLOSE+7:
  883.         case CLOSE+8:
  884.         case CLOSE+9: {
  885.                 register int no;
  886.                 register char *save;
  887.  
  888.                 no = OP(scan) - CLOSE;
  889.                 save = reginput;
  890.  
  891.                 if (regmatch(next)) {
  892.                     /*
  893.                      * Don't set endp if some later
  894.                      * invocation of the same parentheses
  895.                      * already has.
  896.                      */
  897.                     if (regendp[no] == NULL)
  898.                         regendp[no] = save;
  899.                     return(1);
  900.                 } else
  901.                     return(0);
  902.             }
  903.             break;
  904.         case BRANCH: {
  905.                 register char *save;
  906.  
  907.                 if (OP(next) != BRANCH)        /* No choice. */
  908.                     next = OPERAND(scan);    /* Avoid recursion. */
  909.                 else {
  910.                     do {
  911.                         save = reginput;
  912.                         if (regmatch(OPERAND(scan)))
  913.                             return(1);
  914.                         reginput = save;
  915.                         scan = regnext(scan);
  916.                     } while (scan != NULL && OP(scan) == BRANCH);
  917.                     return(0);
  918.                     /* NOTREACHED */
  919.                 }
  920.             }
  921.             break;
  922.         case STAR:
  923.         case PLUS: {
  924.                 register char nextch;
  925.                 register int no;
  926.                 register char *save;
  927.                 register int min;
  928.  
  929.                 /*
  930.                  * Lookahead to avoid useless match attempts
  931.                  * when we know what character comes next.
  932.                  */
  933.                 nextch = '\0';
  934.                 if (OP(next) == EXACTLY)
  935.                     nextch = *OPERAND(next);
  936.                 min = (OP(scan) == STAR) ? 0 : 1;
  937.                 save = reginput;
  938.                 no = regrepeat(OPERAND(scan));
  939.                 while (no >= min) {
  940.                     /* If it could work, try it. */
  941.                     if (nextch == '\0' || *reginput == nextch)
  942.                         if (regmatch(next))
  943.                             return(1);
  944.                     /* Couldn't or didn't -- back up. */
  945.                     no--;
  946.                     reginput = save + no;
  947.                 }
  948.                 return(0);
  949.             }
  950.             break;
  951.         case END:
  952.             return(1);    /* Success! */
  953.             break;
  954.         default:
  955.             regerror = RE_INVALIDPARAMETER;
  956.             return(0);
  957.             break;
  958.         }
  959.  
  960.         scan = next;
  961.     }
  962.  
  963.     /*
  964.      * We get here only if there's trouble -- normally "case END" is
  965.      * the terminating point.
  966.      */
  967.     regerror = RE_INVALIDPARAMETER;
  968.     return(0);
  969. }
  970.  
  971. /*
  972.  - regrepeat - repeatedly match something simple, report how many
  973.  */
  974. static int
  975. regrepeat(p)
  976. char *p;
  977. {
  978.     register int count = 0;
  979.     register char *scan;
  980.     register char *opnd;
  981.  
  982.     scan = reginput;
  983.     opnd = OPERAND(p);
  984.     switch (OP(p)) {
  985.     case ANY:
  986.         count = strlen(scan);
  987.         scan += count;
  988.         break;
  989.     case EXACTLY:
  990.         while (*opnd == *scan) {
  991.             count++;
  992.             scan++;
  993.         }
  994.         break;
  995.     case ANYOF:
  996.         while (*scan != '\0' && strchr(opnd, *scan) != NULL) {
  997.             count++;
  998.             scan++;
  999.         }
  1000.         break;
  1001.     case ANYBUT:
  1002.         while (*scan != '\0' && strchr(opnd, *scan) == NULL) {
  1003.             count++;
  1004.             scan++;
  1005.         }
  1006.         break;
  1007.     default:        /* Oh dear.  Called inappropriately. */
  1008.         regerror = RE_INTERNAL;
  1009.         count = 0;    /* Best compromise. */
  1010.         break;
  1011.     }
  1012.     reginput = scan;
  1013.  
  1014.     return(count);
  1015. }
  1016.  
  1017. /*
  1018.  - regnext - dig the "next" pointer out of a node
  1019.  */
  1020. static char *
  1021. regnext(p)
  1022. register char *p;
  1023. {
  1024.     register int offset;
  1025.  
  1026.     if (p == ®dummy)
  1027.         return(NULL);
  1028.  
  1029.     offset = NEXT(p);
  1030.     if (offset == 0)
  1031.         return(NULL);
  1032.  
  1033.     if (OP(p) == BACK)
  1034.         return(p-offset);
  1035.     else
  1036.         return(p+offset);
  1037. }
  1038.  
  1039. #ifdef DEBUG
  1040.  
  1041. STATIC char *regprop();
  1042.  
  1043. /*
  1044.  - regdump - dump a regexp onto stdout in vaguely comprehensible form
  1045.  */
  1046. void
  1047. regdump(r)
  1048. regexp *r;
  1049. {
  1050.     register char *s;
  1051.     register char op = EXACTLY;    /* Arbitrary non-END op. */
  1052.     register char *next;
  1053.     extern char *strchr();
  1054.  
  1055.  
  1056.     s = r->program + 1;
  1057.     while (op != END) {    /* While that wasn't END last time... */
  1058.         op = OP(s);
  1059.         printf("%2d%s", s-r->program, regprop(s));    /* Where, what. */
  1060.         next = regnext(s);
  1061.         if (next == NULL)        /* Next ptr. */
  1062.             printf("(0)");
  1063.         else 
  1064.             printf("(%d)", (s-r->program)+(next-s));
  1065.         s += 3;
  1066.         if (op == ANYOF || op == ANYBUT || op == EXACTLY) {
  1067.             /* Literal string, where present. */
  1068.             while (*s != '\0') {
  1069.                 putchar(*s);
  1070.                 s++;
  1071.             }
  1072.             s++;
  1073.         }
  1074.         putchar('\n');
  1075.     }
  1076.  
  1077.     /* Header fields of interest. */
  1078.     if (r->regstart != '\0')
  1079.         printf("start `%c' ", r->regstart);
  1080.     if (r->reganch)
  1081.         printf("anchored ");
  1082.     if (r->regmust != NULL)
  1083.         printf("must have \"%s\"", r->regmust);
  1084.     printf("\n");
  1085. }
  1086.  
  1087. /*
  1088.  - regprop - printable representation of opcode
  1089.  */
  1090. static char *
  1091. regprop(op)
  1092. char *op;
  1093. {
  1094.     register char *p;
  1095.     static char buf[50];
  1096.  
  1097.     (void) strcpy(buf, ":");
  1098.  
  1099.     switch (OP(op)) {
  1100.     case BOL:
  1101.         p = "BOL";
  1102.         break;
  1103.     case EOL:
  1104.         p = "EOL";
  1105.         break;
  1106.     case ANY:
  1107.         p = "ANY";
  1108.         break;
  1109.     case ANYOF:
  1110.         p = "ANYOF";
  1111.         break;
  1112.     case ANYBUT:
  1113.         p = "ANYBUT";
  1114.         break;
  1115.     case BRANCH:
  1116.         p = "BRANCH";
  1117.         break;
  1118.     case EXACTLY:
  1119.         p = "EXACTLY";
  1120.         break;
  1121.     case NOTHING:
  1122.         p = "NOTHING";
  1123.         break;
  1124.     case BACK:
  1125.         p = "BACK";
  1126.         break;
  1127.     case END:
  1128.         p = "END";
  1129.         break;
  1130.     case OPEN+1:
  1131.     case OPEN+2:
  1132.     case OPEN+3:
  1133.     case OPEN+4:
  1134.     case OPEN+5:
  1135.     case OPEN+6:
  1136.     case OPEN+7:
  1137.     case OPEN+8:
  1138.     case OPEN+9:
  1139.         sprintf(buf+strlen(buf), "OPEN%d", OP(op)-OPEN);
  1140.         p = NULL;
  1141.         break;
  1142.     case CLOSE+1:
  1143.     case CLOSE+2:
  1144.     case CLOSE+3:
  1145.     case CLOSE+4:
  1146.     case CLOSE+5:
  1147.     case CLOSE+6:
  1148.     case CLOSE+7:
  1149.     case CLOSE+8:
  1150.     case CLOSE+9:
  1151.         sprintf(buf+strlen(buf), "CLOSE%d", OP(op)-CLOSE);
  1152.         p = NULL;
  1153.         break;
  1154.     case STAR:
  1155.         p = "STAR";
  1156.         break;
  1157.     case PLUS:
  1158.         p = "PLUS";
  1159.         break;
  1160.     default:
  1161.         regerror = RE_INVALIDPARAMETER;
  1162.         break;
  1163.     }
  1164.     if (p != NULL)
  1165.         (void) strcat(buf, p);
  1166.     return(buf);
  1167. }
  1168. #endif
  1169.  
  1170.